package com.likou;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Author: 陈桂明
 * Date: 2025/4/23 15:39
 * Description: q84
 */
public class q84 {
    public static void main(String[] args) {
        int area = new q84().largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3});
        System.out.println(area);
    }

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }


//    public int largestRectangleArea(int[] heights) {
//        if (heights.length == 0)
//            return 0;
//        int[] left = new int[heights.length];
//        int[] right = new int[heights.length];
//        int maxArea = 0;
//        for (int i = 0; i < heights.length; i++) {
//            int p = i;
//            while (p > 0 && heights[p - 1] >= heights[i])
//                p = left[p - 1];
//            left[i] = p;
//        }
//        for (int i = heights.length - 1; i >= 0; i--) {
//            int p = i;
//            while (p < heights.length - 1 && heights[p + 1] >= heights[i])
//                p = right[p + 1];
//            right[i] = p;
//        }
//        for (int i = 0; i < heights.length; i++) {
//            int width = right[i] - left[i] + 1;
//            int area = heights[i] * width;
//            maxArea = Math.max(maxArea, area);
//        }
//        return maxArea;
//    }
}
